package org.apache.commons.graph.algorithms.spanning

import org.apache.commons.graph.CommonsGraph.minimumSpanningTree
import org.apache.commons.graph.Graph
import org.apache.commons.graph.SpanningTree
import org.apache.commons.graph.model.*
import org.apache.commons.graph.weight.primitive.DoubleWeightBaseOperations
import org.junit.Assert
import org.junit.Test

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

class PrimTestCase {
    @Test(expected = IllegalStateException::class)
    fun testEmptyGraph() {
        val input = UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>()

        minimumSpanningTree(input)
            .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
            .fromArbitrarySource()
            .applyingPrimAlgorithm(DoubleWeightBaseOperations)
    }

    @Test(expected = IllegalStateException::class)
    fun testNotExistVertex() {
        val input =
            UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>()

        minimumSpanningTree(input)
            .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
            .fromSource(BaseLabeledVertex("NOT EXIST"))
    }

//    @Test(expected = NullPointerException::class)
//    fun testNullGraph() {
//        minimumSpanningTree(null as Graph<BaseLabeledVertex?, BaseLabeledWeightedEdge<Double?>?>?)
//            .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
//            .fromArbitrarySource()
//            .applyingPrimAlgorithm(DoubleWeightBaseOperations)
//    }
//
//    @Test(expected = NullPointerException::class)
//    fun testNullMonoid() {
//        var input: UndirectedMutableGraph<BaseLabeledVertex?, BaseLabeledWeightedEdge<Double?>?>? = null
//        var a: BaseLabeledVertex? = null
//        try {
//            input = UndirectedMutableGraph()
//            a = BaseLabeledVertex("A")
//            input.addVertex(a)
//        } catch (e: NullPointerException) {
//            //try..catch need to avoid a possible test success even if a NPE is thorw during graph population
//            Assert.fail(e.message)
//        }
//
//        minimumSpanningTree(input)
//            .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
//            .fromSource(a)
//            .applyingBoruvkaAlgorithm(null)
//    }
//
//    @Test(expected = NullPointerException::class)
//    fun testNullVertex() {
//        val input =
//            UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>()
//
//        minimumSpanningTree(input)
//            .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
//            .fromSource(null)
//            .applyingPrimAlgorithm(DoubleWeightBaseOperations)
//    }

    /**
     * Test Graph and Prim's solution can be seen on these
     * [slides](http://gauguin.info.uniroma2.it/~italiano/Teaching/Algoritmi/Lezioni/cap12.pdf)
     */
    @Test
    fun testVerifyMinimumSpanningTree2() {
        val input = UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>()

        val a = BaseLabeledVertex("a")
        val b = BaseLabeledVertex("b")
        val c = BaseLabeledVertex("c")
        val d = BaseLabeledVertex("d")
        val e = BaseLabeledVertex("e")
        val f = BaseLabeledVertex("f")
        val g = BaseLabeledVertex("g")

        input.addVertex(a)
        input.addVertex(b)
        input.addVertex(c)
        input.addVertex(d)
        input.addVertex(e)
        input.addVertex(f)
        input.addVertex(g)

        input.addEdge(a, BaseLabeledWeightedEdge("a <-> b", 7.0), b)
        input.addEdge(a, BaseLabeledWeightedEdge("a <-> c", 14.0), c)
        input.addEdge(a, BaseLabeledWeightedEdge("a <-> d", 30.0), d)

        input.addEdge(b, BaseLabeledWeightedEdge("b <-> c", 21.0), c)

        input.addEdge(c, BaseLabeledWeightedEdge("c <-> d", 10.0), d)
        input.addEdge(c, BaseLabeledWeightedEdge("c <-> e", 1.0), e)

        input.addEdge(e, BaseLabeledWeightedEdge("e <-> f", 6.0), f)
        input.addEdge(e, BaseLabeledWeightedEdge("e <-> g", 9.0), g)

        input.addEdge(f, BaseLabeledWeightedEdge("f <-> g", 4.0), g)

        // expected
        val expected =
            MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double>(
                DoubleWeightBaseOperations,
                BaseWeightedEdge()
            )

        for (vertex in input.vertices) {
            expected.addVertex(vertex)
        }

        expected.addEdge(a, BaseLabeledWeightedEdge("a <-> b", 7.0), b)
        expected.addEdge(a, BaseLabeledWeightedEdge("a <-> c", 14.0), c)

        expected.addEdge(c, BaseLabeledWeightedEdge("c <-> d", 10.0), d)
        expected.addEdge(c, BaseLabeledWeightedEdge("c <-> e", 1.0), e)

        expected.addEdge(e, BaseLabeledWeightedEdge("e <-> f", 6.0), f)

        expected.addEdge(f, BaseLabeledWeightedEdge("f <-> g", 4.0), g)

        internalPrimAssertion(
            input,
            a,
            expected
        )
    }

    /**
     * Test Graph and Prim's solution can be seen on
     * [Wikipedia](http://en.wikipedia.org/wiki/Prim%27s_algorithm)
     */
    @Test
    fun testVerifyWikipediaMinimumSpanningTree() {
        val input = UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>()

        val a = BaseLabeledVertex("A")
        val b = BaseLabeledVertex("B")
        val c = BaseLabeledVertex("C")
        val d = BaseLabeledVertex("D")
        val e = BaseLabeledVertex("E")
        val f = BaseLabeledVertex("F")
        val g = BaseLabeledVertex("G")

        input.addVertex(a)
        input.addVertex(b)
        input.addVertex(c)
        input.addVertex(d)
        input.addVertex(e)
        input.addVertex(f)
        input.addVertex(g)

        input.addEdge(a, BaseLabeledWeightedEdge("a <-> b", 7.0), b)
        input.addEdge(a, BaseLabeledWeightedEdge("a <-> d", 5.0), d)

        input.addEdge(b, BaseLabeledWeightedEdge("b <-> c", 8.0), c)
        input.addEdge(b, BaseLabeledWeightedEdge("b <-> d", 9.0), d)
        input.addEdge(b, BaseLabeledWeightedEdge("b <-> e", 7.0), e)

        input.addEdge(c, BaseLabeledWeightedEdge("c <-> e", 5.0), e)

        input.addEdge(d, BaseLabeledWeightedEdge("d <-> e", 15.0), e)
        input.addEdge(d, BaseLabeledWeightedEdge("d <-> f", 6.0), f)

        input.addEdge(e, BaseLabeledWeightedEdge("e <-> f", 8.0), f)
        input.addEdge(e, BaseLabeledWeightedEdge("e <-> g", 9.0), g)

        input.addEdge(f, BaseLabeledWeightedEdge("f <-> g", 11.0), g)

        // expected
        val expected =
            MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double>(
                DoubleWeightBaseOperations,
                BaseWeightedEdge()
            )

        for (vertex in input.vertices) {
            expected.addVertex(vertex)
        }

        expected.addEdge(a, BaseLabeledWeightedEdge("a <-> b", 7.0), b)
        expected.addEdge(a, BaseLabeledWeightedEdge("a <-> d", 5.0), d)
        expected.addEdge(b, BaseLabeledWeightedEdge("b <-> e", 7.0), e)
        expected.addEdge(c, BaseLabeledWeightedEdge("c <-> e", 5.0), e)
        expected.addEdge(d, BaseLabeledWeightedEdge("d <-> f", 6.0), f)
        expected.addEdge(e, BaseLabeledWeightedEdge("e <-> g", 9.0), g)

        internalPrimAssertion(
            input,
            d,
            expected
        )
    }

    companion object {
        private fun internalPrimAssertion(
            input: UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>,
            source: BaseLabeledVertex,
            expected: MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double>
        ) {
            // actual

            val actual: SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> =
                minimumSpanningTree(input)
                    .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
                    .fromSource(source)
                    .applyingPrimAlgorithm(DoubleWeightBaseOperations)

            // assert!
            Assert.assertEquals(expected, actual)
        }
    }
}
